{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Jump Game II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: jump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃游戏 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个长度为 <code>n</code> 的 <strong>0 索引</strong>整数数组 <code>nums</code>。初始位置为 <code>nums[0]</code>。</p>\n",
    "\n",
    "<p>每个元素 <code>nums[i]</code> 表示从索引 <code>i</code> 向前跳转的最大长度。换句话说，如果你在 <code>nums[i]</code> 处，你可以跳转到任意 <code>nums[i + j]</code> 处:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= j &lt;= nums[i]</code>&nbsp;</li>\n",
    "\t<li><code>i + j &lt; n</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回到达&nbsp;<code>nums[n - 1]</code> 的最小跳跃次数。生成的测试用例可以到达 <code>nums[n - 1]</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [2,3,1,1,4]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 跳到最后一个位置的最小跳跃数是 <code>2</code>。\n",
    "&nbsp;    从下标为 0 跳到下标为 1 的位置，跳&nbsp;<code>1</code>&nbsp;步，然后跳&nbsp;<code>3</code>&nbsp;步到达数组的最后一个位置。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [2,3,0,1,4]\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "\t<li>题目保证可以到达&nbsp;<code>nums[n-1]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jump-game-ii](https://leetcode.cn/problems/jump-game-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jump-game-ii](https://leetcode.cn/problems/jump-game-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1,1,4]', '[2,3,0,1,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [None]*n\n",
    "        dp[-1] = 0\n",
    "        for idx in range(n-2, -1, -1):\n",
    "            if nums[idx] == 0: continue\n",
    "            if nums[idx] + idx >= n - 1: \n",
    "                dp[idx] = 1\n",
    "            else:\n",
    "                min_jmps = n\n",
    "                for i in range(idx+nums[idx], 0, -1):\n",
    "                    if dp[i] and dp[i] < min_jmps: min_jmps = dp[i]\n",
    "                dp[idx] = min_jmps + 1\n",
    "        return dp[0]\n",
    "        # steps = [n-1]\n",
    "        # for idx in range(n-2, -1, -1):\n",
    "        #     next_pos = min(n-1, idx + nums[idx])\n",
    "        #     if next_pos >= steps[-1]:\n",
    "        #         print(idx, next_pos)\n",
    "        #         while len(steps) > 1 and next_pos >= min(n-1, steps[-1] + nums[steps[-1]]):\n",
    "        #             steps.pop(-1)\n",
    "        #         steps.append(idx)\n",
    "        #     print(steps)\n",
    "        # return len(steps)-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cnt = 0\n",
    "        i, j = 0, 0\n",
    "        while True:\n",
    "            if j >= len(nums) - 1:\n",
    "                return cnt\n",
    "            m, n = j + 1, j + 1\n",
    "            for k in range(i, j + 1):\n",
    "                n = max(n, nums[k] + k)\n",
    "            i, j = m, n\n",
    "            cnt += 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        self.finished = False\n",
    "        self.steps = 0\n",
    "        # self.jumping(nums, 0)\n",
    "        i = 0\n",
    "        if len(nums) <= 1:\n",
    "            return 0\n",
    "        while True:\n",
    "            farest_index = self.get_farest(nums[i:])\n",
    "            if i+farest_index >= len(nums)-1:\n",
    "                return self.steps+1\n",
    "            else:\n",
    "                i += farest_index\n",
    "                self.steps += 1\n",
    "\n",
    "    def get_farest(self, nums):\n",
    "        farest_index = 0\n",
    "        for i in range(1, nums[0]+1):\n",
    "            if i >= len(nums)-1:\n",
    "                return i\n",
    "            if nums[i] + i > nums[farest_index] + farest_index:\n",
    "                farest_index = i\n",
    "        return farest_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.last = len(nums) - 1\n",
    "        self.step_count = 0\n",
    "        self.nums = nums\n",
    "        self.Traversing()\n",
    "        return self.step_count\n",
    "\n",
    "    def Traversing(self):\n",
    "        search_interval = min(self.nums[0], self.last)\n",
    "        max_jump_within_interval = self.nums[0]\n",
    "        for i in range(1, self.last + 1):\n",
    "            jump = i + self.nums[i]\n",
    "            max_jump_within_interval = max(max_jump_within_interval, jump)\n",
    "\n",
    "            if i == search_interval:\n",
    "                self.step_count += 1\n",
    "                search_interval = min(max_jump_within_interval, self.last)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        if length <= 1:\n",
    "            return 0\n",
    "        dp = [length for _ in range(length)]\n",
    "        dp[0] = 0\n",
    "        center = 0\n",
    "        for i in range(center+1, length):\n",
    "            if nums[center] >= i-center:\n",
    "                dp[i] = dp[center]+1\n",
    "            else:\n",
    "                for j in range(center+1, i):\n",
    "                    if i-j <= nums[j] and dp[i] > dp[j]+1:\n",
    "                        dp[i] = dp[j]+1\n",
    "                        center = j\n",
    "        return dp[length-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) < 2:\n",
    "            return 0\n",
    "        cnt = 0\n",
    "        q = [0]\n",
    "        while True:\n",
    "            cnt += 1\n",
    "            m, n = max(q) + 1, max(q)\n",
    "            for i in q:\n",
    "                n = max(n, i+nums[i])\n",
    "            q = [i for i in range(m, n+1)]\n",
    "            if q[-1] >= len(nums) - 1:\n",
    "                return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        if length <= 1:\n",
    "            return 0\n",
    "        dp = [length for _ in range(length)]\n",
    "        dp[0] = 0\n",
    "        center = 0\n",
    "        for i in range(center+1, length):\n",
    "            if nums[center] >= i-center:\n",
    "                dp[i] = dp[center]+1\n",
    "            else:\n",
    "                for j in range(center+1, i):\n",
    "                    if i-j <= nums[j] and dp[i] > dp[j]+1:\n",
    "                        dp[i] = dp[j]+1\n",
    "                        center = j\n",
    "        print(dp)\n",
    "        return dp[length-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        last = len(nums) - 1\n",
    "        step_count = 0\n",
    "        search_interval = nums[0]\n",
    "        max_jump_within_interval = nums[0]\n",
    "        for i in range(1, last + 1):\n",
    "            jump = i + nums[i]\n",
    "            max_jump_within_interval = max(max_jump_within_interval, jump)\n",
    "\n",
    "            if i == search_interval or i == last:\n",
    "                step_count += 1\n",
    "                search_interval = max_jump_within_interval\n",
    "\n",
    "        return step_count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: 'List[int]') -> 'int':\n",
    "        nn=len(nums)\n",
    "        steps=list(range(nn+1))\n",
    "        #print(steps)\n",
    "        steps[0]=0\n",
    "        if nn==1 :return(0)\n",
    "        maxx=0\n",
    "        n=1\n",
    "        steps[n]=nums[0]\n",
    "        maxx=steps[n]\n",
    "        \n",
    "        while maxx<nn-1:\n",
    "            n+=1\n",
    "            \n",
    "            for i in range(steps[n-2],steps[n-1]+1):\n",
    "                if maxx< i +nums[i]:\n",
    "                    maxx=i+nums[i]\n",
    "            steps[n]=maxx\n",
    "        return(n)\n",
    "                \n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums[-1] = 2 ** 31\n",
    "        nums2, l = [i + j for i, j in enumerate(nums)], len(nums) - 1\n",
    "\n",
    "        def find_max_index(index):\n",
    "            tmp = nums2[index:index + nums[index] + 1]\n",
    "            return index + tmp.index(max(tmp))\n",
    "\n",
    "        index, steps = 0, 0\n",
    "        while True:\n",
    "            index = find_max_index(index)\n",
    "            if index:\n",
    "                steps += 1\n",
    "            if index == l:\n",
    "                break\n",
    "\n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        nums_temp = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            nums_temp.append( i + nums[i] )   \n",
    "        if len(nums_temp) == 1:\n",
    "            return 0\n",
    "        \n",
    "        if max(nums_temp) < len(nums) - 1:\n",
    "            return False\n",
    "\n",
    "        \n",
    "        result = 0\n",
    "        start = 0\n",
    "        end = 0\n",
    "\n",
    "        while True:\n",
    "            end = max(nums_temp[:end + 1])\n",
    "            #k = nums_temp[end]\n",
    "            if end >= len(nums) - 1:\n",
    "                return result + 1\n",
    "                break\n",
    "            result += 1\n",
    "            #start = end + 1\n",
    "            \n",
    "\n",
    "        \n",
    "       \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        if len(nums) == 1: return 0\n",
    "        if len(set(nums)) == 1:\n",
    "            return (len(nums)-2)//nums[0]+1\n",
    "        jumps, start, end, far = 0, 0, 0, 0\n",
    "        while end < len(nums) - 1:\n",
    "            jumps += 1\n",
    "            for i in range(start, end+1):\n",
    "                far = max(far, nums[i]+i)\n",
    "            start, end = end + 1, far\n",
    "        return jumps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def jump(self, nums):\n",
    "#         \"\"\"\n",
    "#         效率过低，无法使用\n",
    "#         从左向右寻找第一个可以到达终点的位置，将该位置设为终点重新寻找下一个位置\n",
    "#         :type nums: List[int]\n",
    "#         :rtype: int\n",
    "#         \"\"\"\n",
    "#         steps = 0\n",
    "#         l = len(nums) - 1\n",
    "#         while l > 0:\n",
    "#             for i in range(l):\n",
    "#                 if i + nums[i] >= l:\n",
    "#                     steps += 1\n",
    "#                     l = i\n",
    "#                     break\n",
    "#         return steps\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def jump(self, nums):\n",
    "#         \"\"\"\n",
    "#         选择可选位置中i+nums[i]最大的位置\n",
    "#         56ms 99.50%\n",
    "#         :type nums: List[int]\n",
    "#         :rtype: int\n",
    "#         \"\"\"\n",
    "#         if len(nums) == 1:\n",
    "#             return 0\n",
    "#         if len(set(nums)) == 1:  # 特殊情况加速判断\n",
    "#             return (len(nums) - 2) // nums[0] + 1\n",
    "#         steps = 0\n",
    "#         pos = 0\n",
    "#         l = len(nums) - 1\n",
    "#         while pos < l:\n",
    "#             temp = pos + nums[pos]\n",
    "#             if temp >= l:\n",
    "#                 return steps + 1\n",
    "#             temp1 = 0\n",
    "#             for i in range(pos + 1, temp + 1):\n",
    "#                 if i + nums[i] >= temp1:\n",
    "#                     temp1 = i + nums[i]\n",
    "#                     pos = i\n",
    "#             steps += 1\n",
    "#         return steps\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        52ms 100%\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        if l == 1:\n",
    "            return 0\n",
    "        if len(set(nums)) == 1:  # 特殊情况加速判断\n",
    "            return (len(nums) - 2) // nums[0] + 1\n",
    "        \n",
    "        steps = last = max_range = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i + num >= l - 1:\n",
    "                return steps + 1\n",
    "            if last < i + num:\n",
    "                last = i + num\n",
    "            if i == max_range and i + 1 < l:\n",
    "                max_range = last\n",
    "                steps += 1\n",
    "        return steps\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\" \n",
    "        if len(nums) == 1: return 0\n",
    "        if len(set(nums)) == 1:\n",
    "            return (len(nums)-2)//nums[0]+1\n",
    "        n = len(nums)-1\n",
    "        idx = 0\n",
    "        step = [0]\n",
    "        while step[-1]+nums[step[-1]]<n:\n",
    "            next_steps = nums[idx+1:idx+nums[idx]+1]\n",
    "            jps = []\n",
    "            for k,v in enumerate(next_steps):\n",
    "                jps.append(k+v)\n",
    "            next_step = jps.index(max(jps))\n",
    "            idx = idx+1+next_step\n",
    "            step.append(idx)\n",
    "        return len(step) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        52ms 100%\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        if l == 1:\n",
    "            return 0\n",
    "        if len(set(nums)) == 1:  # 特殊情况加速判断\n",
    "            return (len(nums) - 2) // nums[0] + 1\n",
    "        \n",
    "        steps = num_where = 0\n",
    "        last = max_range = 0\n",
    "        for i in nums:\n",
    "            if last < num_where + i:\n",
    "                last = num_where + i\n",
    "            if num_where == max_range and num_where + 1 < l:\n",
    "                max_range = last\n",
    "                steps += 1\n",
    "            num_where = num_where + 1\n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def jump(self, nums):\n",
    "#         \"\"\"\n",
    "#         效率过低，无法使用\n",
    "#         从左向右寻找第一个可以到达终点的位置，将该位置设为终点重新寻找下一个位置\n",
    "#         :type nums: List[int]\n",
    "#         :rtype: int\n",
    "#         \"\"\"\n",
    "#         steps = 0\n",
    "#         l = len(nums) - 1\n",
    "#         while l > 0:\n",
    "#             for i in range(l):\n",
    "#                 if i + nums[i] >= l:\n",
    "#                     steps += 1\n",
    "#                     l = i\n",
    "#                     break\n",
    "#         return steps\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def jump(self, nums):\n",
    "#         \"\"\"\n",
    "#         选择可选位置中i+nums[i]最大的位置\n",
    "#         56ms 99.50%\n",
    "#         :type nums: List[int]\n",
    "#         :rtype: int\n",
    "#         \"\"\"\n",
    "#         if len(nums) == 1:\n",
    "#             return 0\n",
    "#         if len(set(nums)) == 1:  # 特殊情况加速判断\n",
    "#             return (len(nums) - 2) // nums[0] + 1\n",
    "#         steps = 0\n",
    "#         pos = 0\n",
    "#         l = len(nums) - 1\n",
    "#         while pos < l:\n",
    "#             temp = pos + nums[pos]\n",
    "#             if temp >= l:\n",
    "#                 return steps + 1\n",
    "#             temp1 = 0\n",
    "#             for i in range(pos + 1, temp + 1):\n",
    "#                 if i + nums[i] >= temp1:\n",
    "#                     temp1 = i + nums[i]\n",
    "#                     pos = i\n",
    "#             steps += 1\n",
    "#         return steps\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def jump(self, nums):\n",
    "        \"\"\"\n",
    "        52ms 100%\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        if l == 1:\n",
    "            return 0\n",
    "        if len(set(nums)) == 1:  # 特殊情况加速判断\n",
    "            return (len(nums) - 2) // nums[0] + 1\n",
    "        \n",
    "        steps = num_where = last = max_range = 0\n",
    "        for num in nums:\n",
    "            if last < num_where + num:\n",
    "                last = num_where + num\n",
    "            if num_where == max_range and num_where + 1 < l:\n",
    "                max_range = last\n",
    "                steps += 1\n",
    "            num_where = num_where + 1\n",
    "        return steps\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: 'List[int]') -> 'int':\n",
    "        L = len(nums)\n",
    "        if L < 2:\n",
    "            return 0\n",
    "        i = 0\n",
    "        CurrentMax = 0\n",
    "        NextMax = 0\n",
    "        level = 0\n",
    "        while CurrentMax - i + 1 > 0:\n",
    "            level += 1\n",
    "            while i <= CurrentMax:\n",
    "                NextMax = max(NextMax, nums[i] + i)\n",
    "                if NextMax >= L - 1:\n",
    "                    return level\n",
    "                i += 1\n",
    "            CurrentMax = NextMax\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: 'List[int]') -> 'int':\n",
    "        if len(nums) <= 1: return 0\n",
    "        l, r = 0, nums[0]\n",
    "        times = 1\n",
    "        while r < len(nums) - 1:\n",
    "            times += 1\n",
    "            nxt = max(i + nums[i] for i in range(l, r + 1))\n",
    "            l, r = r, nxt\n",
    "        return times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: 'List[int]') -> 'int':\n",
    "        if len(nums) <= 1:\n",
    "            return 0\n",
    "        left, right = 0, nums[0]\n",
    "        steps = 1\n",
    "        while right < len(nums) - 1:\n",
    "            steps += 1\n",
    "            next = max(i + nums[i] for i in range(left, right + 1))\n",
    "            left, right = right, next\n",
    "        return steps"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        a = 0\n",
    "        b = 0\n",
    "        for e in nums[:-1]:\n",
    "            if e > b:\n",
    "                b = e\n",
    "            if a == 0:\n",
    "                a = b\n",
    "                res += 1\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        step=0\n",
    "        n=len(nums) \n",
    "        max_path=0\n",
    "        end=0\n",
    "        if n<2:\n",
    "            return 0\n",
    "        for i in range(n-1):\n",
    "            max_path=max(max_path,nums[i]+i)\n",
    "            if end==i:\n",
    "                end=max_path\n",
    "                step+=1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        length = len(nums)\n",
    "        pre = 0\n",
    "        count = 0\n",
    "        while pre < length-1:\n",
    "            count+=1\n",
    "            if length-1 <= nums[pre] + pre:\n",
    "                return count\n",
    "            list2 = nums[pre:nums[pre]+pre+1]\n",
    "            max_ = 0\n",
    "            max_index = 0\n",
    "            for i,j in enumerate(list2):\n",
    "                tem = j + i +pre\n",
    "                if tem > max_:\n",
    "                    max_ = tem\n",
    "                    max_index = i\n",
    "            pre += max_index\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        max_for, end, step = 0, 0, 0\n",
    "        for i in range(len(nums)-1):\n",
    "            if i<=max_for:\n",
    "                max_for = max(max_for, nums[i]+i)\n",
    "                if i==end:\n",
    "                    end = max_for\n",
    "                    step+=1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        ans = [float('inf')] * length\n",
    "        ans[-1] = 0\n",
    "\n",
    "        for i in range(1, length):\n",
    "            # print(ans)\n",
    "            tmp = []\n",
    "            if nums[length - i - 1] == 0:\n",
    "                ans[length - i - 1] = float('inf')\n",
    "            else:\n",
    "                left = length - i\n",
    "                right = length - i - 1 + nums[length - i - 1]\n",
    "                # print(left, right)\n",
    "                right = min(right, length - 1)\n",
    "                tmp = ans[left : right + 1]\n",
    "                # print(tmp, left, right)\n",
    "                ans[length - i - 1] = min(tmp) + 1\n",
    "        # print(ans)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        ans = [float('inf')] * length\n",
    "        ans[-1] = 0\n",
    "\n",
    "        for i in range(1, length):\n",
    "            print(ans)\n",
    "            tmp = []\n",
    "            if nums[length - i - 1] == 0:\n",
    "                ans[length - i - 1] = float('inf')\n",
    "            else:\n",
    "                left = length - i\n",
    "                right = length - i - 1 + nums[length - i - 1]\n",
    "                print(left, right)\n",
    "                right = min(right, length - 1)\n",
    "                tmp = ans[left : right + 1]\n",
    "                print(tmp, left, right)\n",
    "                ans[length - i - 1] = min(tmp) + 1\n",
    "        print(ans)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        pos = len(nums)-1\n",
    "        step = 0\n",
    "        while pos != 0:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] >= pos-i:\n",
    "                    pos = i\n",
    "                    step += 1\n",
    "                    break\n",
    "        return step\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        # dp = [0] * len(nums)\n",
    "        nearestPoint = len(nums)-1\n",
    "        nums[-1] = 0\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            if nums[i] + i >= nearestPoint:\n",
    "                nums[i] = min(nums[i+1:i+nums[i]+1]) + 1\n",
    "                nearestPoint = i\n",
    "            else:\n",
    "                nums[i] = float(inf)\n",
    "            # print(nums[i])\n",
    "\n",
    "        return nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        dp=[inf]*n\n",
    "        dp[0]=0\n",
    "        for i in range(n):\n",
    "            for j in range(1,nums[i]+1):\n",
    "                if i+j<n:\n",
    "                    dp[i+j]=min(dp[i+j],dp[i]+1)\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        if len(nums)<2:\n",
    "            return 0\n",
    "        right=nums[0]\n",
    "        m=right\n",
    "        res=0\n",
    "        for i in range(1,len(nums)):\n",
    "            # if i>right:\n",
    "            #     return False\n",
    "            if right>=len(nums)-1:\n",
    "                return res+1\n",
    "            m=max(m,i+nums[i])\n",
    "            if m>=len(nums)-1:\n",
    "                return res+2\n",
    "            if i==right:\n",
    "                right=m\n",
    "                res+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        cur = 0\n",
    "        nxt = 0\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            nxt = max(nxt, i + nums[i])\n",
    "            if i == cur:\n",
    "                cur = nxt\n",
    "                cnt += 1\n",
    "                if cur >= n-1:\n",
    "                    break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        pre, ans = 0, 0\n",
    "        maxx = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if n == i + 1:\n",
    "                return ans\n",
    "            maxx = max(maxx, i+nums[i]) \n",
    "            if i == pre:\n",
    "                ans += 1\n",
    "                pre = maxx \n",
    "        return ans      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        max_right = 0\n",
    "        step = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            step = max(step,i+nums[i])\n",
    "            if max_right == i:\n",
    "                res += 1\n",
    "                max_right = step\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        now = 0\n",
    "        ans = 0\n",
    "        while now < len(nums) - 1:\n",
    "            right = now + nums[now]\n",
    "            # [now + 1, right] 可达范围\n",
    "            if right >= len(nums) - 1:\n",
    "                return ans + 1\n",
    "            nextRight = right\n",
    "            next = now\n",
    "            for i in range(now + 1, right + 1):\n",
    "                if i + nums[i] > nextRight:\n",
    "                    nextRight = i + nums[i]\n",
    "                    next = i\n",
    "            now = next\n",
    "            ans += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "        step=0\n",
    "        end=0\n",
    "        max_i=0\n",
    "        for i in range (len(nums)-1):\n",
    "            max_i=max(max_i,i+nums[i])\n",
    "            if i ==end:\n",
    "                step+=1\n",
    "                end = max_i\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def jump(self, nums: List[int]) -> int:\n",
    "\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "\n",
    "        dp = [None for _ in range(len(nums))]\n",
    "        dp[0] = 0\n",
    "        for i, n in enumerate(nums):\n",
    "            for j in range(i+1, min(i+n+1, len(nums))):\n",
    "                # print(f\"i={i}, j={j}, dp={dp}\")\n",
    "                if dp[j] is None:\n",
    "                    dp[j] = dp[i] + 1\n",
    "        return dp[-1]\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
